import gmpy2
from Crypto.Util.number import *
from sympy.ntheory.modular import *

n = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810
e = 65537


q_near = gmpy2.iroot(n,2)[0]
while n%q_near!=0:
    q_near=gmpy2.next_prime(q_near)
q = q_near
p = n//q
print(f"p={p}")
print(f"q={q}")

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(m)

import libnum
m1= m*gmpy2.invert(-1,p)%p
print("m1",m1)
m1=m*libnum.invmod(-1,p)%p
print("m1=",m1)
for i in range(p,q):
    m = m*i%q
m2 = m * gmpy2.invert(-1,q) %q
print(m2)
flag = crt([p,q],[m1,m2])[0]
print(flag)
print(long_to_bytes(flag))
